[1] 다음 재귀식의 closed form을 구하시오. 만일 그것이 불가능한 경우에는 [eqn: THETA (`)] order를 대신 구하시오. (20점)

a)  [eqn: T(`1)=```1# T(`n)=``T``(`n/2`)+`3]

(채점 기준)

◾ 아래와 유사한 과정을 통해 [eqn: 1+3log _{2} n]를 도출했으면 10점.

[eqn: T(n) & =T( {n} over {2} )+3# & =T( {n} over {2 ^{2}} )+2 CDOT 3# & =T( {n} over {2 ^{3}} )+3 CDOT 3# & = CDOTS # & =T( {n} over {2 ^{k}} )+k CDOT 3]

[eqn: k=log _{2} n]으로 두면,

[eqn: T(n) & =T( {n} over {2 ^{log _{2} n}} )+(log _{2} n) CDOT 3# & =T(1)+3log _{2} n# & =1+3log _{2} n]

◾ [eqn: THETA (log _{2} n)]만 도출했다면 6점.

◾ [eqn: T(n)=T( {n} over {2} )+3=T( {n} over {4} )+2 CDOT 3=...]까지 전개는 했는데, 잘못 풀이해서 틀렸다면 2∼4점.

b) [eqn: T(`1)=```1# T(`n)=``T``(`n/2`)`+`T(n/3)`+`n]

(채점 기준)

◾ [eqn: 2T(n/3)+n <= T(n) <= 2T(n/2)+n] 등으로 두고 풀어서 어느 한쪽 변 이상을 잘 전개해냈다면 10점.

이 경우 왼쪽을 풀면

[eqn: 2T( {n} over {3} )+n & <= T(n)# 2 ^{2} T( {n} over {3 ^{2}} )+ {2} over {3} n+n & <= # 2 ^{3} T( {n} over {3 ^{3}} )+( {2} over {3} ) ^{2} n+ {2} over {3} n+n & <= # CDOTS & <= # 2 ^{k} T( {n} over {3 ^{k}} )+ sum _{h=0} ^{k-1} ( {2} over {3} ) ^{h} & <= #]

으로 전개되므로 [eqn: THETA (n) <= T(n)]을 얻을 수 있고, 오른쪽을 풀면,

[eqn: T(n) & <= 2T( {n} over {2} )+n# & <= 2 ^{2} T( {n} over {2 ^{2}} )+n+n# & <= CDOTS # & <= 2 ^{k} T( {n} over {2 ^{k}} )+kn]

으로 전개되므로 [eqn: T(n) <= THETA (n`lgn)]을 얻을 수 있음. 이 경우, [eqn: T(n)]이 [eqn: THETA]-표기로 완전히 표현되지 않으나, 일단 양쪽 중 어느 한쪽 이상을 올바르게 전개했다면 점수를 부여함.

◾ [eqn: 2T(n/3)+n <= T(n)]와 같이 처음부터 한쪽으로만 씌워서 전개해 푼 경우에는 8점.

- 단, 성립하지 않는 부등식을 이용해 풀이를 시작한 경우에는 경중에 따라 0∼4점.

예) [eqn: T(n/3)+n <= T(n) <= T(n/2)+n]

◾ [eqn: T(n) & =T( {n} over {2} )+T( {n} over {3} )+n# & =T( {n} over {2 ^{2}} )+2T( {n} over {6} )+T( {n} over {3 ^{2}} )+ {n} over {2} + {n} over {3} +n# & =...]

까지 전개했지만, 그 이후로는 올바르게 풀이를 진행하지 못한 경우 5∼6점.

이처럼 전개해서 풀기 위해서는 아래와 같이 풀어야 함.

[eqn: T(n) & =T( {n} over {2} )+T( {n} over {3} )+n# & =T( {n} over {4} )+2T( {n} over {6} )+T( {n} over {9} )+ {5} over {6} n+n# & =` CDOTS # & =T( {n} over {2 ^{h}} )+ {pmatrix{h#1}} T( {n} over {2 ^{h-1} 3 ^{1}} )+ CDOTS + {pmatrix{h#h-1}} T( {n} over {2 ^{1} 3 ^{h-1}} )+T( {n} over {3 ^{h}} )+( {6} over {5} ) ^{h-1} n+ CDOTS + {5} over {6} n+n]

[eqn: g(h)= sum _{k=0} ^{h-1} ( {5} over {6} ) ^{k} = {1-( {5} over {6} ) ^{h}} over {1- {5} over {6}} =6-6( {5} over {6} ) ^{h}]라 하자.

그러면, [eqn: n CDOT g(h) <= T(n) <= 2 ^{h} T( {n} over {2 ^{h}} )+n CDOT g(h)]라 둘 수 있다.

① [eqn: h=log _{3} n]일 때,

[eqn: g(log _{3} n) & =6-6( {5} over {6} ) ^{log _{3} n} =6-6( {5} over {6} ) ^{{log _{5/6} n} over {log _{5/6} 3}} =6-6n ^{{1} over {log _{5/6} 3}}]이다.

[eqn: n CDOT g(h) & =n CDOT g(log _{3} n)# & =n(6-6n ^{{1} over {log _{5/6} 3}} )# & =6n-6n ^{1+ {1} over {log _{5/6} 3}}]

이때, [eqn: {1} over {log _{5/6} 3} <0]이므로, [eqn: 1+ {1} over {log _{5/6} 3} <1]이다. 따라서,

[eqn: n CDOT g(log _{3} n)=6n-n ^{1- delta } =6n-o(n)= THETA (n)] (단, [eqn: delta =-log _{3} {5} over {6} >0]는 상수)

② [eqn: h=log _{2} n]일 때,

[eqn: 2 ^{h} T( {n} over {2 ^{h}} )+n CDOT g(h) & =2 ^{log _{2} n} T( {n} over {log _{2} n} )+n CDOT g(log _{2} n)# & =nT(1)+n(6-6n ^{{1} over {log _{5/6} 2}} )# & =n+6n-6n ^{1+ {1} over {log _{5/6} 2}}# & =7n-6n ^{1+ {1} over {log _{5/6} 2}}#]

따라서, [eqn: 2 ^{h} T( {n} over {2 ^{h}} )+n CDOT g(h) & =7n-6n ^{1+ {1} over {log _{5/6} 2}} =7n-o(n)= THETA (n)]

그러므로 [eqn: THETA (n) <= T(n) <= THETA (n)]이므로 [eqn: T(n)= THETA (n)].

◾ [eqn: T(n)]의 전개를 올바르게 하지 못한 경우에는 그 경중에 따라 0∼4점.

예)

- [eqn: T(n)=T(n/4)+T(n/6)+T(n/9)+n/2+n/3+n]

- [eqn: T(n)=T(n/4)+2T(n/6)+T(n/9)+n/2+n/3]

- [eqn: T(n)=T(n/4)+2T(n/6)+T(n/9)+3n]

- [eqn: T(n/2)=T(n/4)+T(n/6)+n/2], [eqn: T(n/3)=T(n/6)+T(n/9)+n/3] 등만 적어놓음.

◾ 지나치게 불명확한 풀이방법, 전개를 명백히 잘못하는 등의 경우에는 그 정도에 따라 0∼2점

예)

- [eqn: n/2+n/3=5n/6]이므로 [eqn: THETA (n)]이다: 풀이과정이 명확하지 않음.

- [eqn: T(n/2) APPROX T(n/3)]이므로 [eqn: T(n) APPROX 2T(n/3)+n]: 잘못된 전제
(이후 풀이는 유사할 수 있으나, 부등호를 통해 상하한을 두고 푸는 것과는 근본적으로 다름)

- [eqn: T(n)=T(n/2)+T(n/3)+n=T(n/2 ^{2} )+T(n/3 ^{2} )+n/2+n/3+n= CDOTS]: 완전히 잘못된 전개

[2] 다음의 python code에서 함수 basics( ) 함수의 수행 횟수를 asymptotic order로 제시하시오. 단, 계산과정이 최대한 자세히 기술되어야 한다. 답만 적으면 안 됨. (20점)

N= get_input_size( )

Local = 0

while( N >= 1):

Local = Local + 1

basics( )

for w in range(Local):

N = N - 1

1. 예시 답안

while 반복문 내부에서 N은 증가하는 Local만큼 감소한다.

1씩 증가하는 Local에 대한 basics( ) 함수 수행 횟수 k는 다음과 같다.

[eqn: N``-``(`` UNDERBRACE {k} {1+2+3+...+k} ``)`` = ``0]

[eqn: N- sum _{i=1} ^{k} i``=``N- {k(k+1)} over {2}]

[eqn: k ^{2} +k+ {1} over {4} ``= `` 2N+ {1} over {4}]

[eqn: LEFT ( k+ {1} over {2} RIGHT ) ^{2} = ``2N+ {1} over {4}]

[eqn: k = sqrt { 2N + 1over 4 } - 1 over 2]

[eqn: THEREFORE ```sqrt {N}]

2. 부분점수

[10점]

1) N과 실행 횟수 k 사이의 관계식을 올바르게 작성

k의 제곱으로 구성된 관계식을 작성하면 인정

[5점]

2) while 반복문 내부에서 N, Local 값의 변화를 토대로 수행 횟수 k를 도출

1) 의 관계식이 도출된 과정이 있어야 함

1) 의 관계식을 도출하지 못했어도, 회를 거듭할 때의 N의 감소 또는 수행 횟수 k가 드러나도록 작성하면 인정

[5점]

3) k를 asymptotic order로 제시

- 최종 답에서 [eqn: O, ``Theta] 구분 없이 점수 부여

- 부등호, 상수항, [eqn: N``,``k`]의 계수는 감점 없음, 차수만 고려

[3] N개 중에서 가짜 동전이 1개인 경우

이 복잡도를 [eqn: P(N)]으로 표시하자. 약간 가벼운 가짜 동전이 1개인 경우 base 조건을 계산하면 다음과 같이 나타낼 수 있다.

[eqn: P(1)=0]

[eqn: P(2)=1]

[eqn: P(3)=1]

[eqn: P(4)=2]

[eqn: P(5)=2]

만일 동전이 정확히 3N, 3의 배수 개라면 3등분 된 N개씩을 묶음으로 만들어 찾아보면 어느 묶음에 가짜가 있는지를 1번의 측정으로 알 수 있다. 따라서 그 N개 묶음에서 다시 가짜 동전을 찾는 작업을 recursive 하게 진행하면 된다. 따라서 [eqn: 3N]일 때의 재귀식은 다음과 같다.

[eqn: P(3N)=P(N)+1]

문제는 3의 배수가 아니라 [eqn: 3N+`1,```3N+2]의 경우이다. 만일 [eqn: 3N+1]일 경우, 3개의 N개 뭉치에 가짜 동전이 있을 것이라고 가정하고 찾아본다. 그런데 만일 그 3개의 N개 뭉치에 가짜가 없다는 사실은 제일 마지막 추가 한 번의 저울질로 확인할 수 있다. 3개일 경우를 생각해보자. 만일 1|2를 비교하여 무게가 같을 경우 남은 3번이 가짜인지 진짜인지는 추가 한 번의 저울질이 더 필요하다. 따라서 [eqn: P(3N+1)`=`P(3N)`+``1]이 된다. 이것을 다시 전개하면

[eqn: P(3N+1)`=`P(3N)+1`=` LEFT { `P(N)+1` RIGHT } +`1=P(N)+2]가 된다.

같은 방식으로

[eqn: P(3N+2)=P(3N)+1=P(N)+2]가 된다.

따라서

[eqn: P(3 ^{4} +1)=P(3 ^{4} )+2=4+2=6] 이 된다.

결국 [eqn: P(3 ^{k} +C)=k+P(C) LEQ k+k-1+2=2k+1= THETA (2log _{3} ``N)]이 된다.

[4] N개 중에서 가짜 동전이 2개인 경우

교수님께서 동영상으로 설명한 해설 내용(PLATO에 올려져 있음) 참고

[5] 전자레인지 Jump가 있다. 이 Jump에는 2개의 버튼이 존재한다. 하나는 현재 저장된 시간에 추가 시간을 더하는 Add 버튼이며, 다른 하나는 Add 버튼으로 추가하는 시간의 값을 ‘1’로 되돌리는 Reset 버튼이다. Add 버튼을 누를 때마다 이전에 Add 버튼 더한 값의 2배의 값이 더해진다.

즉, 초기 상태에서 Add 버튼을 4번 누르면 더해지는 값은 1 + 2 + 4 + 8 = 15(초)가 된다. 만일 우리가 음식을 15초 동안 데우려면 초기 상태에서 Add를 4번만 누르면 된다. 그런데 만일 16초로 맞추려면 15초를 만든 다음에 “Reset"을 눌러 Add=1로 만든 다음에 이 상태에서 Add를 눌러 15 + 1 =16을 만들어야 한다.

모든 정수 [eqn: k]에 대하여 Add - Reset - Add - Reset을 누르면 그 시간 [eqn: k]를 맞출 수 있지만, 너무 많이 눌러야 하는 단점이 있다. 여러분은 최소 횟수의 버튼 조작을 통하여 원하는 시간 [eqn: k]를 맞추는 방법을 제시해야 한다. (초기에 Add는 1로 set 되어 있다.)

공통 : 계산과정의 설명이 명확하나 답안에서 ±2의 계산 오차가 있으면 오차의 절댓값만큼 감점(답안 4, 정답 6일 경우 2점 감점). 그 이상의 오차나 미기재된 답안에 대해서는 부분점수 없이 오답처리.

a) [eqn: k=10]을 맞추기 위한 최소의 버튼(Add, Reset 모두) 조작 횟수를 구하는 방법을 설명하시오. (10점)

A^X = A를 X 번 누르는 동작이라고 정의, V(A^X)는 A^X로 더해지는 값

V(A^(X+1))은 V(A^X) * 2 + 1이고, V(A^X) 와 V(A^(X+1)) 사이의 값은 모두 X+1 이상의
동작 횟수를 요구하므로 임의의 정수 N을 만드는 최소 횟수는 V(A^X)의 꼴을 가지는
값의 합으로 구성되는 그리디 알고리즘이 최적.

따라서 N보다 작은 최대의 V(A^X)를 계속 빼면서 목표 수치를 달성하는 방법을 사용.

A^3 R A^2 -> V(A^3) + V(A^2) = 7+3으로 총 6회 동작으로 10을 완성

b) [eqn: k=100]을 맞추기 위한 최소의 버튼(Add, Reset 모두) 조작 횟수를 구하는 방법을 설명하시오. (10점)

A^6 R A^5 R A^2 R A^2 -> 63 + 31 + 3 + 3, 총 18회 동작으로 100을 완성

c) [eqn: k=1000]을 맞추기 위한 최소의 버튼(Add, Reset 모두) 조작 횟수를 구하는 방법을 설명하시오. (10점)

A^9 R A^8 R A^7 R A^6 R A^5 R A^3 R A^2 R A^2 -> 511 + 255 + 127 + 63 + 31 + 7 + 3 + 3, 총 49회 동작으로 1000을 완성

d) 일반적인 N에 대하여 최소의 버튼(Add, Reset 모두) 조작 횟수를 N의 점근적 함수

[eqn: THETA (N)]으로 구하시오. (그 과정을 보여야 합니다. ) (10점)

best case : N = V(A^X), worst case : N = V(A^X) + V(A^(X-1)) + ... + V(A)

[eqn: K= LFLOOR log _{2} N RFLOOR]이라고 정의할 때,

[eqn: 0 <= K+1 <= theta (N) <= (K+1)+K+(K-1)+ CDOTS +1+K=(K ^{2} +5K+2)/2]

양변의 K의 차수가 다르므로 Theta로 표현 불가능, [eqn: O((log _{2} N) ^{2} )]이 정답.

worst case에 대한 계산 설명이 타당할 경우 정답처리, 답만 맞을 경우 5점

[6] 초콜릿 공장의 컨베이어 벨트에서 아래와 같이 한 칸 단위 초콜릿이 한 줄로 나온다. 우리는 이것을 적당한 길이의 묶음으로 잘라 포장하여 판매한다. 그런데 공정 중에 문제가 생겨서 어떤 단위 초콜릿은 흠이 있는 불량품(F로 표시)이 될 수도 있다. 따라서 불량품이 포함된 초콜릿 상품은 약간 싼 값에 판매된다.

초콜릿의 포장 단위는 단위 초콜릿 2개 묶음, 또는 3개 묶음, 즉 [eqn: 1` TIMES `2, ````1 times 3], 이렇게 2종이다. 단위 초콜릿 1개는 포장비용을 고려해서 판매하지 않는다. 종류별 가격(단위:천원)은 다음과 같다. 불량인 단위 초콜릿의 위치는 어디에 있든지 상관이 없다.

모두 정상         모두 정상          1개 불량           1개 불량

F

	F

4                 7                  3                 5

초콜릿 순서가 아래와 같은 경우 우리가 얻을 수 있는 최대 이익을 계산하여 아랫줄 빈 칸에 작성하시오.
(풀이 과정에서 Dynamic programming 점화식이 분명하게 제시되어야 한다. )

a)

1	2	3	4	5	6
		F		F
0	4	5	7	8	10

b)

1	2	3	4	5	6	7	8	9	10
		F			F	F
0	4	5	7	9	10	10	13	15	17

c) 10번까지는 b)와 같으므로 앞의 결과를 활용하면 된다.

1	2	3	4	5	6	7	8	9	10	11	12	13	14
		F			F	F					F
0	4	5	7	9	10	10	13	15	17	20	20	23	25

1. 예시 답안

각 index (1~N)에서 가질 수 있는 최대 이익에 대한 DP table을 dp[]라 하면,

dp[n]에 대한 Dynamic programming 점화식은 다음과 같이 표현된다.

dp[n] = [eqn: rm max {cases{rm `dp`[n-1]#`dp`[n-2]+ alpha #`dp`[n-3]+ beta }} it]

[eqn: rm alpha = {cases{4````````[n-1,`n]`구간에`F`=`0#3````````[n-1,`n]`구간에`F`=`1#0````````[n-1,`n]`구간에`F`=`2}}] , [eqn: rm beta = {cases{7````````[n-2,`n]`구간에`F`=``0#5````````[n-2,`n]`구간에`F`=``1#0````````[n-2,`n]`구간에`F` GEQ 2}}]

2. 부분점수

[10점]

1) DP 점화식을 올바르게 작성

일반화한 점화식 대신 풀어 설명해도 인정

- 포함하지 않는 구간이 있거나, 알아보기 어려운 경우 감점

점화식이나 설명이 없고, 풀이과정만 있는 경우 5점

[9점]

2) 각 DP table의 마지막 빈칸을 올바르게 작성

- 각 3점, 총 9점

[11점]

3) DP table의 빈칸을 올바르게 작성

틀린 칸의 수를 따져 감점(올림 처리)

ex) a) - 1개, b) - 3개, c) - 4개 => 총 8개 틀린 경우
=> 8/30 *11 = 88/30 = 3점 감점

ex) a) - 2개, b) - 3개, c) - 4개 => 총 9개 틀린 경우

=> 9/30 *11 = 99/30 = 4점 감점